[BAEKJOON] 14267. 내리 칭찬

문제 :

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.

모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.

직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오.

입력 :

첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)

사장은 상사가 없으므로 칭찬을 받지 않는다.

출력 :

1번부터 n번의 직원까지 칭찬을 받은 정도를 출력하시오.

풀이 :

21년 1월 1일은 DP로 문을 열었따…! 하핳… 정말 즐겁구먼(?)

우선 본 문제는 사실 dp연습을 한다고 dp 분류 문제로 풀긴했지만 내 주관적인 생각으로는 그렇게 dp스러운 문제같진 않은 것 같다.

• 처음에는 내리 칭찬을 계산하기 전 부하들의 연결도를 살펴보면 트리 구조가 만들어지기 때문에 트리 자료구조를 구현해서 풀어야하는 생각을 했다.
• 두번째로는 트리 구조는 딱히 필요없는 것 같아 구현은 따로 하지 않았으며(하지만 트리의 구조를 이해하면 문제 접근이 쉬운 것 같긴 하다.) 각 부하들이 받는 칭찬을 계산해둔 후 각 노드들에서 루트(가장 높은 상사)까지 칭찬을 더해가면서 구해주면 어떨까 생각했다. 하지만 회사 직원 수가 10만 명 이하이기 때문에 최대 깊이를 가지는 트리 형태가 형성되버리면 시간 복잡도가 매우 높아질 것 같았다.
• 아마 본 문제의 의도가 여기서 dp 방식을 활용하라는 것 같았다. 각 노드별로 지속적으로 칭찬 점수를 반복 계산해줄 필요 없이 무조건 각 노드의 상사는 그 노드 인덱스보다 낮은 인덱스라는 조건이 있기 때문에 낮은 인덱스부터 차례로 내리칭찬 점수를 계산해주면 반복과정을 할 필요가 없어진다.

코드 :

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, fir, sec, i;
    cin >> n >> m;
    int *order = new int[n + 1];
    int *compliment = new int[n + 1]{0};
    for (i = 1; i <= n; i++)
        cin >> order[i];
    for (i = 0; i < m; i++) {
        cin >> fir >> sec;
        compliment[fir] += sec;
    }
    cout << "0 ";
    for (i = 2; i <= n; i++) {
        compliment[i] += compliment[order[i]];
        cout << compliment[i] << ' ';
    }
    cout << '\n';
    return 0;
}